home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / gnu / gawk / gawk213b.zoo / test / lisp / walk.ms < prev    next >
Text File  |  1991-05-21  |  15KB  |  504 lines
  1. .\" troff -ms
  2. .\" ...if no CW font available, change CW to B globally
  3. .de ZB
  4. .DS
  5. .ft CW
  6. .nf
  7. ..
  8. .de ZE
  9. .DE
  10. .ft R
  11. .fi
  12. .br
  13. ..
  14. .TL 
  15. A LISP interpreter in Awk
  16. .AU
  17. Roger Rohrbach
  18. .AI
  19. 1592 Union St.,  #94
  20. San Francisco,  CA 94123
  21. .ND
  22. January 3,  1989
  23. .AB ABSTRACT
  24. .PP
  25. This note describes a simple interpreter for the LISP programming
  26. language,  written in \fBawk\fR.  It provides
  27. intrinsic versions of the basic functions on s-expressions,  and many others
  28. written in LISP.  It is compatible with the commonly
  29. available version of \fBawk\fR that is
  30. supplied with most UNIX systems.  The interpreter serves to illustrate
  31. the use of \fBawk\fR for prototyping or implementing language
  32. translators,  as well as providing a simple example of LISP
  33. implementation techniques.
  34. .AE
  35. .SH
  36. Intrinsic functions.
  37. .PP
  38. The interpreter has thirteen built-in functions.
  39. These include the five elementary functions on s-expressions defined
  40. by McCarthy [1];  some conditional expression operators;  an
  41. assignment operator,  and some functions to control the evaluation process.
  42. .PP
  43. The intrinsic functions are summarized below.
  44. Familiarity with existing LISP systems is assumed in the
  45. descriptions of these functions.
  46. .IP "\f(CW(car \fIl\fP)\fR"
  47. .br
  48. Returns the first element of the list \fIl\fR.
  49. An error occurs if \fIl\fR is atomic.
  50. .IP "\f(CW(cdr \fIl\fP)\fR"
  51. .br
  52. Returns the remainder of the list \fIl\fR,  \fIi.e.\fR,
  53. the sublist containing the second through the last
  54. elements.  If \fIl\fR has only one element,  \fBnil\fR is
  55. returned.  \fBcdr\fR is undefined on atoms.
  56. .IP "\f(CW(cons \fIe l\fP)\fR"
  57. .br
  58. Constructs a new list whose \fBcar\fR is \fIe\fR
  59. and whose \fBcdr\fR is \fIl\fR.
  60. .IP "\f(CW(eq \fIx y\fP)\fR"
  61. .br
  62. Returns \fBt\fR if \fIx\fR and \fIy\fR
  63. are the same LISP object,  \fIi.e.\fR,  are either atomic and
  64. have the same print name,  or evaluate to the same
  65. list cell.  Otherwise,  \fBnil\fR is returned.
  66. .IP "\f(CW(atom \fIs\fP)\fR"
  67. .br
  68. Returns \fBt\fR if \fIs\fR is an atom,  otherwise \fBnil\fR.
  69. .IP "\f(CW(set \fIx y\fP)\fR"
  70. .br
  71. Assigns the value \fIy\fR to \fIx\fR and returns \fIy\fR.
  72. \fIx\fR must be atomic,  and may not be a constant
  73. or name an intrinsic function.
  74. .IP "\f(CW(eval \fIs\fP)\fR"
  75. .br
  76. Evaluates \fIs\fR and returns the result.
  77. .IP "\f(CW(error \fIs\fP)\fR"
  78. .br
  79. Halts evaluation and returns \fBnil\fR.
  80. The atom \fIs\fR is printed.
  81. .IP "\f(CW(quote \fIs\fP)\fR"
  82. .br
  83. Returns \fIs\fR,  unevaluated.  The form
  84. .ZB
  85. \'\fIexpr\fP
  86. .ZE
  87. is an abbreviation for
  88. .ZB
  89. (quote \fIexpr\fP)
  90. .ZE
  91. .IP "\f(CW(cond (\fIp1 \f(CW[\fIe1\f(CW]) \fI...\fP (\fIpN \f(CW[\fIeN\f(CW]))\fR"
  92. .br
  93. Evaluates each \fIp\fR from left to right.  If any
  94. evaluate to a value other than \fBnil\fR,  the
  95. corresponding \fIe\fR is evaluated and the result is returned.
  96. If there is no corresponding \fIe\fR,  the value of the \fIp\fR
  97. itself is returned instead.
  98. If no \fIp\fR has a non-null value,  \fBnil\fR is returned.
  99. .IP "\f(CW(and \fIe1 ...  eN\fP)\fR"
  100. .br
  101. Evaluates each \fIe\fR and returns \fBnil\fR if any evaluate to \fBnil\fR.
  102. Otherwise  the value of the last \fIe\fR is returned.
  103. .IP "\f(CW(or \fIe1 ...  eN\fP)\fR"
  104. .br
  105. Evaluates each \fIe\fR and returns the first whose
  106. value is non-null.  If no such \fIe\fR is found,  \fBnil\fR is returned.
  107. .IP "\f(CW(list \fIe1 ...  eN\fP)\fR"
  108. .br
  109. Constructs a new list with elements \fIe1 ...  eN\fR.
  110. Equivalent to
  111. .br
  112. \f(CW(cons \fIe1\fP (cons \fI...\fP (cons \fIeN\fP nil)\fR.
  113. .SH
  114. Lambda functions.
  115. .PP
  116. The following functions are written in LISP and are
  117. defined in the file \fBwalk.w\fR.  Most of
  118. these are commonly supplied with LISP systems.
  119. .IP "\f(CW(cadr \fIs\fP)\fR"
  120. .IP "\f(CW(cddr \fIs\fP)\fR"
  121. .IP "\f(CW(caar \fIs\fP)\fR"
  122. .IP "\f(CW(cdar \fIs\fP)\fR"
  123. .IP "\f(CW(cadar \fIs\fP)\fR"
  124. .IP "\f(CW(caddr \fIs\fP)\fR"
  125. .IP "\f(CW(cddar \fIs\fP)\fR"
  126. .IP "\f(CW(cdadr \fIs\fP)\fR"
  127. .br
  128. These correspond to various compositions of
  129. \fBcar\fR and \fBcdr\fR,  \fIe.g.\fR,
  130. .br
  131. \f(CW(cadr \fIs\fP)\fR \(-> \f(CW(car (cdr \fIs\fP))\fR.
  132. .IP "\f(CW(null \fIs\fP)\fR"
  133. .br
  134. Equivalent to \f(CW(eq \fIs\fP nil)\fR.
  135. .IP "\f(CW(not \fIs\fP)\fR"
  136. .br
  137. Same as \fBnull\fR.
  138. .IP "\f(CW(ff \fIs\fP)\fR"
  139. .br
  140. Returns the first atomic symbol in \fIs\fR.
  141. .IP "\f(CW(subst \fIx y z\fP)\fR"
  142. .br
  143. Substitutes \fIx\fR for all occurrences of the atom \fIy\fR in \fIz\fR.
  144. \fIx\fR and \fIz\fR are arbitrary s-expressions.
  145. .IP "\f(CW(equal \fIx y\fP)\fR"
  146. .br
  147. Returns \fBt\fR if \fIx\fR and \fIy\fR are
  148. the same s-expression,  otherwise \fBnil\fR.
  149. .IP "\f(CW(append \fIx y\fP)\fR"
  150. .br
  151. Creates a new list containing the elements of x and y,
  152. which must both be lists.
  153. .IP "\f(CW(member \fIx y\fP)\fR"
  154. .br
  155. Returns \fBt\fR if \fIx\fR is an element of the list \fIy\fR,
  156. otherwise \fBnil\fR.
  157. .IP "\f(CW(pair \fIx y\fP)\fR"
  158. .br
  159. Pairs each element of the lists \fIx\fR and \fIy\fR,
  160. and returns a list of the resulting pairs.  The number
  161. of pairs in the result will equal the length of the
  162. shorter of the two input lists.
  163. .IP "\f(CW(assoc \fIx y\fP)\fR"
  164. .br
  165. Association list selector function.
  166. \fIy\fR is a list of the
  167. form \f(CW((\fIu1\fP \fIv1\fP) \fI...\fP (\fIuN\fP \fIvN\fP))\fR
  168. where the \fIu\fR's are atomic.  If \fIx\fR is
  169. one of these,  the corresponding pair \f(CW(\fIu\fP \fIv\fP)\fR
  170. is returned,  otherwise \fBnil\fR.
  171. .IP "\f(CW(sublis \fIx y\fP)\fR"
  172. .br
  173. \fIx\fR is an association list.
  174. Substitutes the values in \fIx\fR for the keys in \fIy\fR.
  175. .IP "\f(CW(last \fIl\fP)\fR"
  176. .br
  177. Returns the last element of \fIl\fR.
  178. .IP "\f(CW(reverse \fIl\fP)\fR"
  179. .br
  180. Returns a list that contains the elements in \fIl\fR,
  181. in reverse order.
  182. .IP "\f(CW(remove \fIe l\fP)\fR"
  183. .br
  184. Returns a copy of \fIl\fR with all
  185. occurrences of the element \fIe\fR removed.
  186. .IP "\f(CW(succ \fIx y\fP)\fR"
  187. .br
  188. Returns the element that immediately follows the atom \fIx\fR
  189. in the list \fIy\fR.  If \fIx\fR does not occur in \fIy\fR
  190. or is the last element,  \fBnil\fR is returned.
  191. .IP "\f(CW(pred \fIx y\fP)\fR"
  192. .br
  193. Returns the element that immediately precedes the atom \fIx\fR
  194. in the list \fIy\fR.  If \fIx\fR does not occur in \fIy\fR
  195. or is the first element,  \fBnil\fR is returned.
  196. .IP "\f(CW(before \fIx y\fP)\fR"
  197. .br
  198. Returns the list of elements occurring before y in x.
  199. If \fIy\fR does not occur in \fIx\fR
  200. or is the first element,  \fBnil\fR is returned.
  201. .IP "\f(CW(after \fIx y\fP)\fR"
  202. .br
  203. Returns the list of elements occurring after y in x.
  204. If \fIy\fR does not occur in \fIx\fR
  205. or is the last element,  \fBnil\fR is returned.
  206. .IP "\f(CW(plist \fIx\fP)\fR"
  207. .br
  208. Returns the property list for the atom \fIx\fR.
  209. .IP "\f(CW(get \fIx i\fP)\fR"
  210. .br
  211. Returns the value stored on \fIx\fR's property list
  212. under the indicator \fIi\fR.
  213. .IP "\f(CW(putprop \fIx v i\fP)\fR"
  214. .br
  215. Stores the value \fIv\fR on \fIx\fR's property list under
  216. the indicator \fIi\fR.
  217. .IP "\f(CW(remprop \fIx i\fP)\fR"
  218. .br
  219. Remove the indicator \fIi\fR
  220. and any associated value from \fIx\fR's property list.
  221. .IP "\f(CW(mapcar \fIf l\fP)\fR"
  222. .br
  223. Applies the function \fIf\fR to each element of \fIl\fR and returns
  224. the list of results.
  225. .IP "\f(CW(apply \fIf args\fP)\fR"
  226. .br
  227. Calls \fIf\fR with the arguments \fIargs\fR,  \fIe.g.\fR,
  228. .ZB
  229. (apply 'cons '(a (b)))
  230. .ZE
  231. is equivalent to
  232. .ZB
  233. (cons 'a '(b))
  234. .ZE
  235. .SH
  236. Syntactic conventions.
  237. .LP
  238. Atoms take the following forms:
  239. .IP "\fIRegular identifiers\fR"
  240. .br
  241. Atoms matching the regular expression
  242. .br
  243. .sp
  244. .nf
  245.     \f(CW[_A-Za-z][-A-Za-z_0-9]*\fR
  246. .fi
  247. .sp
  248. The initial value of an identifier is \fBnil\fR.
  249. .IP "\fIIntegers\fR"
  250. .br
  251. Atoms matching the regular expression \f(CW[0-9][0-9]*\fR.
  252. Integers are constants,  \fIi.e.\fR,  evaluate to themselves.
  253. .IP "\fIWeird atoms\fR"
  254. .br
  255. Identifiers matching the regular expression \f(CW".*"\fR.  Weird
  256. atoms are not constants.
  257. .LP
  258. A semicolon introduces a comment,  which continues for the rest
  259. of the line.
  260. .SH
  261. Usage.
  262. .LP
  263. The command for running the interpreter is
  264. .ZB
  265. walk [ \fIfiles\fP ]
  266. .ZE
  267. on BSD UNIX and derivative systems,  or
  268. .ZB
  269. awk -f walk [ \fIfiles\fP ]
  270. .ZE
  271. on UNIX System V.
  272. The file name \f(CW\-\fR represen